/************************************************************************

								Heroes IV
					  Copyright 2000, The 3DO Company

	------------------------------------------------------------------
  						       clip_list.h

	$Header: /game/clip_list.h $

	$NoKeywords: $

 ************************************************************************/

#ifndef CLIP_LIST_H_INCLUDED
#define CLIP_LIST_H_INCLUDED

#if _MSC_VER > 1000
#pragma once
#endif // _MSC_VER > 1000

#include <algorithm>
#include <list>
#include "screen_point.h"
#include "counted_ptr.h"

//t_rect_list_cache : used to reduce the constant overheard of allocating and freeing t_screen_rects
//has to be counted to ensure proper order of destruction.

namespace k_global_freelist_const
{
	const int k_delete_list_rect_limit = 10000;
	const int k_global_pre_alloc_limit = 5000;
};

class t_rect_list_cache : public t_counted_object
{
public:

	t_rect_list_cache();
	virtual ~t_rect_list_cache();

	void push_front_use_free_list( std::list<t_screen_rect> & rect_lists, t_screen_rect const & rect );
	void push_back_use_free_list( std::list<t_screen_rect> & rect_lists, t_screen_rect const & rect );
	void clear_rect_list( std::list<t_screen_rect> & rect_lists );
	void add_to_free_list( std::list<t_screen_rect> & m_rects, std::list<t_screen_rect>::iterator & iter );

private:
	
	std::list<t_screen_rect>		m_rects_free;

};

typedef t_counted_ptr<t_rect_list_cache>		t_rect_list_cache_ptr;

t_rect_list_cache_ptr	get_global_free_rect_list();

inline void t_rect_list_cache::push_back_use_free_list( std::list<t_screen_rect> & rect_lists, t_screen_rect const & rect )
{
	//rect_lists.push_back(rect);
	//return;

	if (m_rects_free.size() == 0)
	{
		rect_lists.push_back( rect );
	}
	else
	{
		std::list<t_screen_rect>::iterator iter = m_rects_free.begin();
		
		*iter = rect;
		
		rect_lists.splice(rect_lists.end(),m_rects_free,iter);
	}
	
	if (m_rects_free.size() > k_global_freelist_const::k_delete_list_rect_limit)
	{
		m_rects_free.clear();
		m_rects_free.resize(k_global_freelist_const::k_global_pre_alloc_limit);
	}
}

inline void t_rect_list_cache::push_front_use_free_list( std::list<t_screen_rect> & rect_lists, t_screen_rect const & rect )
{
	//rect_lists.push_front(rect);
	//return;

	if (m_rects_free.size() == 0)
	{
		rect_lists.push_back( rect );
	}
	else
	{
		std::list<t_screen_rect>::iterator iter = m_rects_free.begin();

		*iter = rect;
		
		rect_lists.splice(rect_lists.begin(),m_rects_free,iter);
	}
	
	if (m_rects_free.size() > k_global_freelist_const::k_delete_list_rect_limit)
	{
		m_rects_free.clear();
		m_rects_free.resize(k_global_freelist_const::k_global_pre_alloc_limit);
	}
}

inline void t_rect_list_cache::clear_rect_list( std::list<t_screen_rect> & rect_lists )
{
	//rect_lists.clear();
	//return;

	if (rect_lists.size() != 0)
		m_rects_free.splice(m_rects_free.begin(),rect_lists,rect_lists.begin(),rect_lists.end());
}

inline void t_rect_list_cache::add_to_free_list( std::list<t_screen_rect> & m_rects, std::list<t_screen_rect>::iterator & iter )
{
	//m_rects.erase (iter) ;
	//return;

	m_rects_free.splice(m_rects_free.begin(),m_rects,iter);
}

// ---------------------------------------------------------------
// object to maintain a list of valid rectangles for drawing
// ---------------------------------------------------------------
class t_clip_list
{
public:
	typedef std::list<t_screen_rect>::iterator       t_iterator;
	typedef std::list<t_screen_rect>::const_iterator t_const_iterator;

	t_clip_list();
	t_clip_list( t_screen_rect const& rect );
	~t_clip_list();

	template<class iterator>
	t_clip_list( iterator first, iterator last  )
	{
		m_global_free_rect_list = get_global_free_rect_list();

		while (first != last)
		{	
			m_global_free_rect_list->push_back_use_free_list(m_rects,*first);
			
			first++;
		}
		
		update_extent();
	}

    t_clip_list(const t_clip_list& clist);
    t_clip_list& operator=(const t_clip_list& clist);

	t_iterator           begin();        // get start of list
	t_const_iterator     begin() const;
	void                 clear();
	bool                 contains( t_screen_rect const& rect ) const;
	bool                 empty() const;
	t_iterator           end();          // get end of list
	t_const_iterator     end() const;
	t_screen_rect const& get_extent() const;
	void                 intersect( t_screen_rect const& rect ); // remove non-intersecting regions
	void                 intersect( t_clip_list const& regions );
	bool                 intersects( t_screen_rect const& rect ) const;
	void                 merge_rectangles();                     // attempt to merge 1st rect
	void                 offset( t_screen_point const& point );  // move entire region
	void                 swap( t_clip_list & other );

	bool         operator == (t_clip_list const& regions) const;
	t_clip_list& operator -= (t_screen_rect const& rect);
	t_clip_list& operator -= (t_clip_list const& regions);
	t_clip_list& operator += (t_screen_rect const& rect);
	t_clip_list& operator += (t_clip_list const& regions);

protected:

	bool remove( t_screen_rect const& rect );   // internal support function for rect removal
	bool remove( t_clip_list const& regions );  // internal support function for region removal
	void update_extent();                       // force an extent recalculation

	t_screen_rect            m_extent;
	t_rect_list_cache_ptr	 m_global_free_rect_list;
	std::list<t_screen_rect> m_rects;

	friend t_clip_list intersection( t_clip_list const & first, t_screen_rect const & second );
	friend void		   intersection_cached( t_clip_list & first, t_clip_list & second, t_screen_rect const & third );

};

inline t_clip_list::t_iterator t_clip_list::begin()
{
  return m_rects.begin();
}

inline t_clip_list::t_const_iterator t_clip_list::begin() const
{
  return m_rects.begin();
}

inline bool t_clip_list::empty() const
{
	return m_rects.empty();
}

inline t_clip_list::t_iterator t_clip_list::end()
{
  return m_rects.end();
}

inline t_clip_list::t_const_iterator t_clip_list::end() const
{
  return m_rects.end();
}

inline t_screen_rect const& t_clip_list::get_extent() const
{
  return m_extent;
}

inline void t_clip_list::swap( t_clip_list & other )
{
	std::swap( m_extent, other.m_extent );
	m_rects.swap( other.m_rects );
}

inline bool contains( t_screen_rect const& rect, t_clip_list const& clip_list )
{
  return rect.contains( clip_list.get_extent() );
}

t_clip_list intersection( t_clip_list const & first, t_screen_rect const & second );
void		intersection_cached( t_clip_list & first, t_clip_list & second, t_screen_rect const & third );

inline t_clip_list intersection( t_screen_rect const & first, t_clip_list const & second )
{
	return intersection( second, first );
}

#endif // CLIP_LIST_H_INCLUDED